Mathematics in the Real World by W.D. Wallis

Author:W.D. Wallis
Language: eng
Format: epub, pdf
Publisher: Springer New York, New York, NY

A proper coloring is called an n-coloring if it uses n colors; if G has an n-coloring, then G is called n-colorable. So the Four-Color Theorem says that every planar graph is four-colorable.

The chromatic number χ(G) of a graph G is the smallest integer n such that G has an n-coloring. A coloring of G in χ(G) colors is called minimal. We use the phrase “G is n-chromatic” to mean that χ(G) = n (but note that a minority of authors use n-chromatic as a synonym for n-colorable).

Incidentally, ξ and χ are the Greek letters “xi” and “chi.” In Greek words, ξ is pronounced like ks in English, while χ has a ch sound.

A cycle of length v has chromatic number 2 if v is even and 3 if v is odd. The star K 1,n has chromatic number 2. Clearly χ(G) = 1 if G has no edges and χ(G) ≥ 2 if G has at least one edge. The complete graph on n vertices has chromatic number n.

There are two useful results when looking for chromatic numbers. The first is that, if the graph G has a subgraph H, then χ(G) cannot be smaller than χ(H). The second, known as Brooks’ Theorem, says that if G is any graph other than a complete graph or a cycle of odd length, then the chromatic number of a graph G is never greater than the maximum degree in G; however, it can be less.

There is no good algorithm to color a graph in the minimum number of colors. One method, sequential coloring, proceeds as follows. First, list the vertices in some order. (The usual method is to arrange the vertices in order of increasing degree.) Apply color 1 to the first vertex in the list. Delete that vertex and all its neighbors, and apply color 1 to the first remaining vertex. Again, delete that vertex and all its neighbors. Continue until the list is empty. Then delete all vertices that received color 1, and apply the same technique to the new list, using color 2. And so on.

The sequential coloring method usually gives a good result, but not necessarily a minimal coloring. For example, consider the 6-cycle abcdef. It can be colored in two colors (with color classes {ace} and {bdf}), but if the vertices are listed as a,d,c,f,b,e three colors will be needed.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.